package main

func main() {
	
}
//#link: https://leetcode-cn.com/problems/find-eventual-safe-states/
func eventualSafeNodes(graph [][]int) (ans []int) {
	n := len(graph)
	//三色标记 0:白色 1:灰色 2:黑色
	color := make([]int, n)
	var safe func(int) bool

	safe = func(x int) bool {
		//已经染过色之后，判断是否等于2
		if color[x] > 0 {
			return color[x] == 2
		}
		//先染色为灰色
		color[x] = 1
		for _, y := range graph[x] {
			if !safe(y) {
				return false
			}
		}
		//染为黑色，标识安全
		color[x] = 2
		return true
	}
	for i := 0; i < n; i++ {
		if safe(i) {
			ans = append(ans, i)
		}
	}
	return
}

